1. Field of the Invention
The present invention relates to a Montgomery multiplier, and more particularly, a Montgomery multiplier for an RSA security module secured from a differential power analysis attack.
2. Description of the Background Art
With the rapid growth of the internet and the electronic commerce, smart cards have been widely used as personal authentication solutions for the electronic commerce such as internet banking, electronic cash, medical cards and traffic cards. Because they can safely store personal information, personal keys and personal certificates, necessity and demand for the smart cards are increasing drastically. Especially, different from general magnetic cards, the smart cards containing microprocessors and memory functions show excellent physical security and safely store personal information. In addition, the smart cards can be used as multifunctional cards including memory, operation and security functions.
Generally public key encryption is applied to the smart cards and the RSA algorithm suggested by R. L. Rivest, A. Shamir and L. Adleman in 1978 has been known as the representative public key encryption.
The RSA encryption algorithm is performed by modular operations based on integers over 1024 bits. Security of the RSA encryption algorithm results from difficulty of factorization in prime factors of large integer coefficients. The RSA encryption algorithm is briefly explained as follows. Two different decimals ‘p’ and ‘q’ are designated as personal keys. The product of ‘p’ and ‘q’ n(=pq) and an arbitrary integer ‘e’ that is relatively prime from φ(n) are designated as public keys. Here, φ(n) represents a number of elements relatively prime from ‘n’. In addition, ‘d’ satisfying e·d=1 (mod φ(n)) is calculated and used as a personal key. That is, ‘p’, ‘q’ and ‘d’ are personal keys and ‘n’ and ‘e’ are public keys.
In encryption, a plain text M is calculated as an encrypt text C=Me mod n by using the public key ‘e’, and calculated as a decrypt text M=Cd mod n. As described above, the RSA security module performs encryption and decryption by taking modular exponentiation to the pubic or personal key. The modular exponentiation is consecutive modular multiplications and the modular multiplication is consecutive additions. Normally used is a Montgomery algorithm that does not have to consider carry delay in the operation. For example, a Montgomery multiplier actually performs ABR−1 mod N instead to calculate AB mod N, wherein R is an integer relatively prime from N and larger than N.
However, side channel information that is not considered in encryption algorithm design for the smart cards exists. The side channel information is classified into time differential information showing time operation differences in an operation of a microprocessor, signal information leaked from a power line, mis-operation information caused by defect inputs, and information by electromagnetic leakage, and etc.
Smart card attack techniques by side channels are generally called side channel attacks, and divided into a time differential attack by time differential information, an defect input attack by defect mis-operation information, an electromagnetic leakage attack by the electromagnetic leakage information, and a power analysis attack by power line leakage information.
Here, the power analysis attack means a password decryption technique by which binary codes of various information is read by measuring instantaneous voltage (power) variations of an IC chip when an encryption algorithm and a secret key for encryption built in the card start to operate, and important information is analyzed according to a statistical method, and forged/modulated as well. The power analysis attack is classified into a simple power analysis attack, a differential power analysis attack, an inference power analysis attack and a high-degree differential power analysis attack. Especially, the differential power analysis attack can estimate the secret key merely by using a few devices for measuring voltage variations. Accordingly, the differential power analysis attack is deemed to be more efficient than a brute-force attack using an exclusive encryption device or a super computer.
FIGS. 1A and 1B are circuit diagrams illustrating a structure and operation of a synchronous XOR circuit generally applied to the Montgomery multiplier.
TABLE 1AIN—TRUEBIN—TRUEOUTTRUE000011101110
Referring to FIG. 1A, an XOR gate 10 receives two input signals AIN—TRUE and BIN—TRUE as shown in Table 1. When the two input values are different, the XOR gate 10 outputs a logical high value, and when the two input values are identical, the XOR gate 10 outputs a logical low value.
In FIG. 1B, the gate-level synchronous XOR circuit of FIG. 1A is designed in a transistor level.
As illustrated in FIG. 1B, the synchronous XOR circuit includes the first P type transistor P101 and the first N type transistor N101 driven by the first input signal A1 and connected in series between a power supply node and a ground node, the second P type transistor P102 and the second N type transistor N102 driven by the voltage applied to the output node of the first P type transistor P101 and connected in series between the power supply node and the ground node, the third P type transistor P103 and the third N type transistor N103 driven by the second input signal A2 and connected in series between the power supply node and the ground node, the fourth P type transistor P104 driven by the voltage applied to the output node of the third P type transistor P103 and receiving the voltage applied to the output node of the second P type transistor P102, the fourth N type transistor N104 driven by the second input signal A2 and receiving the voltage applied to the output node of the second P type transistor P102, the fifth P type transistor P105 driven by the second input signal A2 and receiving the voltage applied to the output node of the first P type transistor P101, the fifth N type transistor P105 driven by the voltage applied to the output node of the third P type transistor P103 and receiving the voltage applied to the output node of the first P type transistor P101, and the sixth P type transistor P106 and the sixth N type transistor N106 driven by the voltage applied to the output node of the fourth P and N type transistors P104 and N104 and the output node of the fifth P and N type transistors P105 and N105, and connected in series between the power supply node and the ground node. The output node of the sixth P type transistor P106 outputs the final output value.
Still referring to FIG. 1B, when the output value OUTTRUE is low, five of the ten transistors are turned on, but when the output value OUTTRUE is high, three of them are turned on. That is, in the synchronous XOR circuit, the number of the switched transistors is changed according to the input values, and thus power consumption is changed. Such power difference makes the module weak to the differential power analysis attack.
Required is an operation logic for solving the problems of the synchronous XOR circuit applied to the Montgomery multiplier, and minimizing correlations between internally-operated binary data and power consumption patterns.
FIG. 2 shows a data representation method by a synchronous single line method and an asynchronous double line method.
By the synchronous single line method, the data is represented as logical high or low states according to binary data ‘0’ or ‘1’. For example, as shown in FIG. 2, data ‘0100110’ represents, three logical high states and four logical high states according to input of a clock signal.
On the other hand, by the asynchronous double line method, two lines DATAFALSE and DATATRUE are used to represent one binary data. In order to represent binary data ‘0’, a logical high signal is applied to the DATAFALSE line, and a logical low signal is applied to the DATATRUE line. Conversely, to represent binary data ‘1’, a logical low signal is applied to the DATAFALSE line, and a logical high signal is applied to the DATATRUE line.
In the case that the data is represented by the asynchronous double line method, whatever the binary data value is, the same number of logical high states and logical low states are generated. Accordingly, whatever binary data is to be operated, power consumption difference of the circuit is minimized.
When the RSA security module is formed by using the aforementioned characteristics of the asynchronous double line method, the differential power analysis attack can be defended.
FIGS. 3A to 3C are circuit diagrams illustrating a structure and operation of an asynchronous XOR circuit.
As shown in FIG. 3A, all items that can be generated by two input binary data AIN—TRUE, AIN—FALSE, BIN—TRUE and BIN—FALSE are generated by C-element devices 20, 22, 24 and 26, and the outputs from the C-element devices 20, 22, 24 and 26 are combined by OR gates 30 and 32.
FIG. 3B is an exemplary diagram illustrating transistor-level design of the C-element devices 20, 22, 24 and 26 of FIG. 3A. The C-element device 20 includes the first to the fifth P type transistors P201, P202, P203, P204 and P205, and the first to the fifth N type transistors N201, N202, N203, N204 and N205. FIG. 3C is an exemplary diagram illustrating transistor-level design of the OR gates 30 and 32 of FIG. 3A. The OR gate 30 is driven by the output signals C1 and C2 from the two C-element devices 20 and 22, and includes the first to the third P type transistors P301, P302 and P303 and the first to the third N type transistors N301, N302 and N303.
In the asynchronous XOR circuit, the number of the switched transistors is not changed according to the input values. However, since excessively many C-element devices are used, large space for the circuit is needed.